package kyssion.leetcode.num101_150;


import java.util.Arrays;

public class code115_不同的子序列 {

    public static void main(String[] args) {
        System.out.println(new code115_不同的子序列().numDistinct(
                "babgbag", "bag"
        ));
    }

    public int numDistinct(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }
        if (t.length() >= s.length()) {
            return t.equals(s) ? 1 : 0;
        }
        char[] ts = t.toCharArray();
        char[] ss = s.toCharArray();
        int[][] dp = new int[ts.length][ss.length];
        for (int a = 0; a < ts.length; a++) {
            for (int b = a; b < ss.length; b++) {
                if (a != 0) {
                    if (ts[a] == ss[b]) {
                        dp[a][b] = dp[a - 1][b - 1] + dp[a][b - 1];
                    } else {
                        dp[a][b] = dp[a][b - 1];
                    }
                } else {
                    if (ts[a] == ss[b]) {
                        dp[a][b] = b == 0 ? 1 : dp[a][b - 1] + 1;
                    } else {
                        dp[a][b] = b == 0 ? 0 : dp[a][b - 1];
                    }
                }
            }
        }
        return dp[ts.length - 1][ss.length - 1];
    }

    public int numDistinct2(String s, String t) {
        // dp[0]表示空串
        int[] dp = new int[t.length() + 1];
        // dp[0]永远是1，因为不管S多长，都只能找到一个空串，与T相等
        dp[0] = 1;

        //t的字典
        int[] map = new int[128];
        Arrays.fill(map, -1);

        //从尾部遍历的时候可以遍历 next类似链表 无重复值时为-1，
        //有重复时例如从rabbit的b开始索引在map[b] = 2 next[2] 指向下一个b的索引为3
        // for (int j = t.length() - 1; j &gt;= 0; j--) {
        //     if (t.charAt(j) == s.charAt(i)) {
        //        dp[j + 1] += dp[j];
        //     }
        // }
        //这段代码的寻址就可以从map[s.charAt(i)] 找到索引j 在用next[j] 一直找和 s.charAt(i)相等的字符 其他的就可以跳过了
        //所以这个代码的优化 关键要理解 上面的一维倒算
        int[] nexts = new int[t.length()];
        for(int i = 0 ; i < t.length(); i++){
            int c = t.charAt(i);
            nexts[i] = map[c];
            map[c] = i;
        }

        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            for(int j = map[c]; j >= 0; j = nexts[j]){
                dp[j + 1] += dp[j];
            }
        }
        return dp[t.length()];
    }
}
